<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,200分)- 猜密码（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>小杨申请了一个保密柜&#xff0c;但是他忘记了密码。只记得密码都是数字&#xff0c;而且所有数字都是不重复的。</p> 
<p>请你根据他记住的数字范围和密码的最小数字数量&#xff0c;帮他算下有哪些可能的组合&#xff0c;<strong>规则如下</strong>&#xff1a;</p> 
<ol><li>输出的组合都是从可选的数字范围中选取的&#xff0c;且不能重复&#xff1b;</li><li>输出的密码数字要按照从小到大的顺序排列&#xff0c;密码组合需要按照字母顺序&#xff0c;从小到大的顺序排序。</li><li>输出的每一个组合的数字的数量要大于等于密码最小数字数量&#xff1b;</li><li>如果可能的组合为空&#xff0c;则返回“None”</li></ol> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入的第一行是可能的密码数字列表&#xff0c;数字间以半角逗号分隔<br /> 输入的第二行是密码最小数字数量</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>可能的密码组合&#xff0c;每种组合显示成一行&#xff0c;每个组合内部的数字以半角逗号分隔&#xff0c;从小到大的顺序排列。</p> 
<p>输出的组合间需要按照字典序排序。<br /> 比如&#xff1a;2,3,4放到2,4的前面</p> 
<p></p> 
<h4>备注</h4> 
<p>字典序是指按照单词出现在字典的顺序进行排序的方法&#xff0c;比如&#xff1a;</p> 
<ul><li>a排在b前</li><li>a排在ab前</li><li>ab排在ac前</li><li>ac排在aca前</li></ul> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">2,3,4<br /> 2</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">2,3<br /> 2,3,4<br /> 2,4<br /> 3,4</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>最小密码数量是两个&#xff0c;可能有三种组合&#xff1a;<br /> 2,3<br /> 2,4<br /> 3,4</p> <p>三个密码有一种&#xff1a;<br /> 2,3,4</p> </td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td>输入</td><td>2,0<br /> 1</td></tr><tr><td>输出</td><td>0<br /> 0,2<br /> 2</td></tr><tr><td>说明</td><td>可能的密码组合&#xff0c;一个的有两种:<br /> 0<br /> 2<br /> 两个的有一个:<br /> 0,2</td></tr></tbody></table> 
<p> </p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题是一道求组合问题。可以利用回溯算法求解。</p> 
<p></p> 
<p>本题求组合时有如下要求&#xff1a;</p> 
<ul><li>组合元素个数 ≥ 密码最小数字数量&#xff08;第二个输入&#xff09;</li><li>组合内元素需要按照数值大小升序</li><li>组合不重复&#xff08;树层去重&#xff09;</li></ul> 
<p></p> 
<p>输出时&#xff1a;</p> 
<ul><li>如果有多个组合&#xff0c;则多个组合需要按照字典序升序</li><li>如果没有组合&#xff0c;输出&#34;None&#34;</li></ul> 
<p></p> 
<p>另外本题没有说明输入的数字是否为单位数&#xff0c;因此需要考虑多位数情况。</p> 
<p></p> 
<p>本题中树层去重的逻辑可以参考&#xff1a;</p> 
<p><a href="https://blog.csdn.net/qfc_128220/article/details/127710678?ops_request_misc&#61;%257B%2522request%255Fid%2522%253A%2522170316715616800215076654%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&amp;request_id&#61;170316715616800215076654&amp;biz_id&#61;0&amp;utm_medium&#61;distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-127710678-null-null.nonecase&amp;utm_term&#61;%E7%AF%AE%E7%90%83%E6%AF%94%E8%B5%9B&amp;spm&#61;1018.2226.3001.4450" title="华为OD机试 - 篮球比赛&#xff08;Java &amp; JS &amp; Python &amp; C&#xff09;-CSDN博客">华为OD机试 - 篮球比赛&#xff08;Java &amp; JS &amp; Python &amp; C&#xff09;-CSDN博客</a></p> 
<p></p> 
<h4 style="background-color:transparent;">Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  static int[] nums;
  static int level;

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    nums &#61; Arrays.stream(sc.nextLine().split(&#34;,&#34;)).mapToInt(Integer::parseInt).toArray();
    level &#61; Integer.parseInt(sc.nextLine());

    System.out.println(getResult());
  }

  public static String getResult() {
    // 按照数值大小升序&#xff0c;这样后续形成的组合的内部就是按照数值大小升序的
    Arrays.sort(nums);

    // 求不重复组合
    ArrayList&lt;String&gt; res &#61; new ArrayList&lt;&gt;();
    dfs(0, new LinkedList&lt;&gt;(), res);

    if (res.size() &gt; 0) {
      // 组合间按照字典序排序
      res.sort(String::compareTo);
      return String.join(&#34;\n&#34;, res);
    } else {
      return &#34;None&#34;;
    }
  }

  public static void dfs(int index, LinkedList&lt;String&gt; path, ArrayList&lt;String&gt; res) {
    if (path.size() &gt;&#61; level) {
      // 如果path层数到达level层&#xff0c;则记录该组合
      res.add(String.join(&#34;,&#34;, path));
    }

    for (int i &#61; index; i &lt; nums.length; i&#43;&#43;) {
      // 树层去重
      if (i &gt; 0 &amp;&amp; nums[i] &#61;&#61; nums[i - 1]) continue;

      path.add(nums[i] &#43; &#34;&#34;);
      dfs(i &#43; 1, path, res);
      path.removeLast();
    }
  }
}
</code></pre> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81" style="background-color:transparent;">JS算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

// 输入处理
void (async function () {
  const nums &#61; (await readline()).split(&#34;,&#34;).map(Number);
  const level &#61; parseInt(await readline());
  console.log(getResult(nums, level));
})();

function getResult(nums, level) {
  // 按照数值大小升序&#xff0c;这样后续形成的组合的内部就是按照数值大小升序的
  nums.sort((a, b) &#61;&gt; a - b);

  // 求不重复组合
  const res &#61; [];
  dfs(nums, 0, level, [], res);

  if (res.length &gt; 0) {
    // 组合间按照字典序排序
    return res.sort().join(&#34;\n&#34;);
  } else {
    return &#34;None&#34;;
  }
}

function dfs(nums, index, level, path, res) {
  if (path.length &gt;&#61; level) {
    // 如果path层数到达level层&#xff0c;则记录该组合
    res.push(path.join(&#34;,&#34;));
  }

  for (let i &#61; index; i &lt; nums.length; i&#43;&#43;) {
    // 树层去重
    if (i &gt; 0 &amp;&amp; nums[i] &#61;&#61; nums[i - 1]) continue;

    path.push(nums[i]);
    dfs(nums, i &#43; 1, level, path, res);
    path.pop();
  }
}
</code></pre> 
<p></p> 
<h4 style="background-color:transparent;">Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
nums &#61; list(map(int, input().split(&#34;,&#34;)))
level &#61; int(input())


def dfs(index, path, res):
    if len(path) &gt;&#61; level:
        # 如果path层数到达level层&#xff0c;则记录该组合
        res.append(&#34;,&#34;.join(map(str, path)))

    for i in range(index, len(nums)):
        # 树层去重
        if i &gt; 0 and nums[i] &#61;&#61; nums[i - 1]:
            continue

        path.append(nums[i])
        dfs(i &#43; 1, path, res)
        path.pop()


# 算法入口
def getResult():
    # 按照数值大小升序&#xff0c;这样后续形成的组合的内部就是按照数值大小升序的
    nums.sort()

    # 求不重复组合
    res &#61; []
    dfs(0, [], res)

    if len(res) &gt; 0:
        # 组合间按照字典序排序
        res.sort()
        return &#34;\n&#34;.join(res)
    else:
        return &#34;None&#34;


# 调用算法
print(getResult())
</code></pre> 
<p></p> 
<p> </p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>